package com.llb666.java.leetcode.array;

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.List;

/**
 * 一个正整数数组nums(非空，非null)里面的数范围在【1，nums.length】之间。
 * 这个数组里所有数要么出现一次，要么出现两次，返回所有出现两次的数（顺序任意）
 *      ※ 希望只遍历一次
 *      ※ 希望用常数的存储空间
 * @author liulibin
 * 2021/9/8 10:57
 */
public class 找到所有重复的数 {
    //假设一个数是x,我们用nums[x-1]的符号来表示其是否出现过
    public static void main(String[] args) {
        int[] c = new int[] {1,3,2,6,2,3};
        List<Integer> integers = method1(c);
        integers.forEach(System.out::println);
    }
    // 直接计数，用了多余的空间
    private static  List<Integer> method1(int[] nums) {
        int[] c = new int [nums.length];
        List<Integer> r = new ArrayList<>();
        for (int x : nums) {
            if (++c[x - 1] == 2) {
                r.add(x);
            }
        }
        return r;
    }

    private static  List<Integer> method2(int[] nums) {
        List<Integer> r = new ArrayList<>();
        for (int x : nums) {
            final int ind = Math.abs(x) - 1;
            if (nums[ind] < 0) {
                r.add(ind + 1);
            }
            nums[ind] = -nums[ind];
        }
        return r;
    }
}
